#include <stdio.h>
#include <malloc.h>
#include <queue>
#include <vector>
#define MaxSize 100

typedef char ElemType;

typedef struct tnode {
    ElemType data;	//数据域
    struct tnode *lchild,*rchild;	//指针域
} BTNode;

// 根据括号表示的二叉树字符串创建二叉树
// leftstr 是指向当前待处理字符的指针
BTNode* CreateBTree(char *&leftstr) {
    if (*leftstr  == '\0') {
        return NULL;	//空树
    }
    BTNode *p = (BTNode *)malloc(sizeof(BTNode));
    p->data = *leftstr;	//取出当前结点数据
    p->lchild = p->rchild = NULL;	//初始化左右孩子指针
    leftstr++;
    // 判断当前结点是否有子树
    if (*leftstr == '(') {
        leftstr++;
        // 若有左子树，递归创建左子树
        if (*leftstr != ',') {
            p->lchild = CreateBTree(leftstr);
        }
        // 若有右子树，递归创建右子树
        if (*leftstr == ',') {
            leftstr++;
            p->rchild = CreateBTree(leftstr);
        }
    }
    // 跳过右括号
    if (*leftstr == ')') {
        leftstr++;
    } 
    return p;
}

void DispBTree(BTNode *bt) {
    if (bt != NULL) {
        printf("%c", bt->data);
        if (bt->lchild != NULL || bt->rchild != NULL) {
            printf("(");	//有子树时输出'('
            DispBTree(bt->lchild);	//递归处理左子树
            if (bt->rchild != NULL)	//有右子树时输出'，'
                printf(",");
            DispBTree(bt->rchild);	//递归处理右子树
            printf(")");	//子树输出完毕，再输出一个')'
        }
    }
}

void DestroyBTree(BTNode *&bt) {
    if (bt != NULL) {
        DestroyBTree(bt->lchild);
        DestroyBTree(bt->rchild);
        free(bt);
    }
}

int BTHeight(BTNode *bt) {
    int lchilddep, rchilddep;
    if (bt == NULL) return(0);	//空树的高度为0
    else {
        lchilddep = BTHeight(bt->lchild);	//求左子树的高度为lchilddep
        rchilddep = BTHeight(bt->rchild);	//求右子树的高度为rchilddep
        return (lchilddep > rchilddep) ? (lchilddep + 1) : (rchilddep + 1);
    }
}

int NodeCount(BTNode *bt) {	//求二叉树bt的结点个数
    int num1, num2;
    if (bt == NULL)	//空树返回0
        return 0;
    else {
        num1 = NodeCount(bt->lchild);	//求左子树结点个数
        num2 = NodeCount(bt->rchild);	//求右子树结点个数
        return (num1 + num2 + 1);	//返回和加上1
    }
}

int LeafCount(BTNode *bt) {	//求二叉树bt的叶子结点个数
    int num1, num2;
    if (bt == NULL)	//空树返回0
        return 0;
    else if (bt->lchild == NULL && bt->rchild == NULL)
        return 1;	//叶子结点时返回1
    else {
        num1 = LeafCount(bt->lchild);	//求左子树叶子结点个数
        num2 = LeafCount(bt->rchild);	//求右子树叶子结点个数
        return (num1 + num2);	//返回和
    }
}


void PrintBlank(int n) {
    for (int i = 0; i < n; i++) {
        printf(" ");	//打印n个空格
    }
}

// 将二叉树bt的结点按层次存入数组levelNodes中，
// idx表示当前结点在数组中的位置，
void LinkedTree2Vector(BTNode *bt, std::vector<BTNode *> &levelNodes, const int idx) {
    if (bt == NULL) return;	//空树返回
    levelNodes[idx] = bt;	//将当前结点存入数组
    LinkedTree2Vector(bt->lchild, levelNodes, 2 * idx + 1);	//递归处理左子树
    LinkedTree2Vector(bt->rchild, levelNodes, 2 * idx + 2);	//递归处理右子树

}

// 以字符方式绘制二叉树bt的图形，
/*
层|左|中
1|8|-|        A
2|4|7|    B       C
3|2|3|  D   E   F   G
4|1|1| H I J K L M N O
*/
void DrawTree(BTNode *bt) {
    if (bt == NULL) return;	//空树返回
    int height = BTHeight(bt);	//计算树的高度
    int maxNum = (1 << height) - 1;	//计算树的最大结点数

    std::vector<BTNode *> levelNodes(maxNum, NULL);
    LinkedTree2Vector(bt, levelNodes, 0);	//获取当前层的节点

    for (int level = 1; level <= height; level++) {
        int leftBlank = 1 << (height - level);	//计算当前层的左侧空格数
        int midBlank = (1 << (height - level + 1)) - 1;	//计算当前层的中间空格数
        PrintBlank(leftBlank);    //打印左侧空格
        int start = (1 << (level - 1)) - 1;	//当前层的起始位置
        int end = (1 << level) - 2;	//当前层的结束位置
        for (int i = start; i <= end; i++) {
            if (levelNodes[i] != NULL) {
                printf("%c", levelNodes[i]->data);	//打印当前节点数据
            } else {
                printf(" ");	//打印空格
            }
            PrintBlank(midBlank);	//打印中间空格
        }
        printf("\n");
    }
}
